import com.chy.线程.b;
import jdk.nashorn.internal.objects.NativeFloat32Array;
import org.junit.Test;

import java.io.*;
import java.lang.reflect.Array;
import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.net.InetAddress;
import java.net.UnknownHostException;
import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.Future;
import java.util.concurrent.FutureTask;

public class test {
    @Test
    public void test1(){
        int[] a = {2,4,3,1,4};
        int[] duplication = new int[1];
        duplicate(a,5,duplication);

    }
    @Test
    public void test2(){
        System.out.println(Sum_Solution(5));
        System.out.println(6/2);
        int[] a = {1,2,3,4};
        reOrderArray(a);
        List<String> titleList = new ArrayList<String>();
        titleList.add("1");
        titleList.add("12");
        titleList.add("13");
        titleList.add("14");
        String[] newArr = titleList.toArray(new String[titleList.size()]);
        //Integer[] newArr2 = titleList.toArray(new Integer[titleList.size()]);
        //String [] objects = (String[]) titleList.toArray();
        System.out.println(newArr);
        //Arrays.toString();
        //Stack s1;
        Queue q = new LinkedList<String>();
        q.add("1");
        q.add("2");
        q.add("3");
        q.offer("3");
        System.out.println(q);
    }

    @Test
    public void test03(){
        //add()和remove()方法在失败的时候会抛出异常(不推荐)
        Queue<String> queue = new LinkedList<String>();
        //添加元素
        queue.offer("a");
        queue.offer("b");
        queue.offer("c");
        queue.offer("d");
        queue.offer("e");
        System.out.println(queue);
        for(String q : queue){
            System.out.print(q);
        }
        System.out.println("===");
        System.out.println("poll="+queue.poll()); //返回第一个元素，并在队列中删除
        for(String q : queue){
            System.out.print(q);
        }
        System.out.println("===");
        System.out.println("element="+queue.element()); //返回第一个元素
        for(String q : queue){
            System.out.print(q);
        }
        System.out.println("===");
        System.out.println("peek="+queue.peek()); //返回第一个元素
        for(String q : queue){
            System.out.print(q);
        }
        System.out.println(runningSum(new int[]{1, 2, 3, 4}));
    }

    public int[] runningSum(int[] nums) {
//        int[] temp = Arrays.copyOf(nums,nums.length);
//        for(int i=1;i<nums.length;i++){
//            int sum = 0;
//            for(int j=0;j<i;j++){
//                sum += temp[j];
//            }
//            nums[i] += sum;
//        }
//        return nums;
        int temp[] = new int[nums.length];
        temp[0] = nums[0];
        for(int i = 1;i < nums.length ;i++){
            temp[i] = temp[i-1] + nums[i];
        }
        return temp;


    }
    @Test
    public void test04(){
        Stack stack1 = new Stack();
        Stack stack2 = new Stack();
        stack1.push("1");
        stack1.push("2");
        Object pop = stack1.pop();
        System.out.println(pop);
        shuffle(new int[]{2, 5, 1, 3, 4, 7}, 3);
        System.out.println(kidsWithCandies(new int[]{12, 1, 12}, 10));
        numJewelsInStones("ac","bhc");
        System.out.println(subtractProductAndSum(234));
        System.out.println(minCount(new int[]{4, 2, 1}));
        System.out.println(decompressRLElist(new int[]{1,1,2,3}));
        System.out.println(numberOfSteps(14));
        createTargetArray(new int[]{0,1,2,3,4},new int[]{0,1,2,2,1});
        /**
         *  1 ， 1
         *  3 ， 4
         * -1 ， 0
         */
        minTimeToVisitAllPoints(new int[][]{{1,1},{3,4},{-1,0}});
        System.out.println(removeOuterParentheses("(()())(())"));
        System.out.println(hammingDistance(4, 1));
        canMakeArithmeticProgression(new int[]{-30,-16,-156,-170,-114,-184,-86,-72,-44,-58,-100,-128,-142,-2});
    }
    @Test
    public void test05(){
        oddCells(2,3,new int[][]{{0,1},{1,1}});
        nextGreaterElement(new int[]{4,1,2},new int[]{1,3,4,2});
        matrixReshape(new int[][]{{1,2},{3,4}},1,4);
//        String S = "abcde";
//        String substring = S.substring(0, 0);
//        substring +=  S.substring(2,5);
//        System.out.println(substring);
//        System.out.println(removeDuplicates("abbaca"));
        System.out.println(removeDuplicates("abbbabaaa"));
        reverseString(new char[]{'a','b','c'});
        maximum69Number(9996);
        TreeNode t1 = new TreeNode(1);
//        TreeNode t2 = new TreeNode(2);
//        TreeNode t3 = new TreeNode(1);
//        t1.left = t2;
//        t1.right = t3;
        TreeNode t4 = new TreeNode(0);
//        TreeNode t5 = new TreeNode(1);
//        TreeNode t6 = new TreeNode(2);
//        t4.left = t5;
//        t4.right = t6;
        isSameTree(null,t4);
        int l = 10;
        char str = '1';
        System.out.println(l%str);
        System.out.println(selfDividingNumbers(10, 22));
        freqAlphabets("8910#11#12");
        System.out.println((char)('a'+1));
        System.out.println(heightChecker(new int[]{1, 1, 4, 2, 1, 3}));
        List<Integer> list = Arrays.asList(1, 2, 3);
//        OutputStreamWriter outputStreamWriter = new OutputStreamWriter();
//        BufferedOutputStream bufferedOutputStream = new BufferedOutputStream(new FileOutputStream());
//        BufferedReader bufferedReader = new BufferedReader()
        int a = 1;
    }
    @Test
    public void test06() throws UnknownHostException, ExecutionException, InterruptedException {
        InetAddress address = InetAddress.getByName("192.168.3.52");
        //public String getHostName()：获取此IP地址的主机名
         String name = address.getHostName();
        // public String getHostAddress()：返回文本显示中的IP地址字符串
        String ip = address.getHostAddress();
        System.out.println("主机名：" + name);
        System.out.println("IP地址：" + ip);
        System.out.println("//n\\");
        System.out.println(arrayPairSum(new int[]{1, 4, 3, 2}));
        System.out.println(1 % 1);
        System.out.println(divisorGame(3));
        System.out.println(sortString("aabbcc"));
        HashMap map = new HashMap();
        Queue queue = new LinkedList();
        queue.poll();
        FutureTask futureTask = new FutureTask(new b());
        Thread thread = new Thread(futureTask);
        thread.start();
        System.out.println(futureTask.get());
        System.out.println(Math.floor(-11.0));
        System.out.println(7 | 3);
        String aa = "ab"; // 放在常量池中
        String bb = "ab"; // 从常量池中查找
        if (aa == bb) // true
            System.out.println("aa==bb");
//        aa.equals();
//        RuntimeException;
//        FutureTask
//        wycwxgjipg
    }
    @Test
    public void test07(){
        String a = "hh";
        String b = "hh";
        System.out.println(a==b);
        Set list = new HashSet();
        boolean add = list.add(null);
        boolean add2 = list.add(null);
        System.out.println(add+"!!"+add2);
        for (Object o : list) {
            list.remove(o);
        }
        System.out.println(list);
        System.out.println(luckyNumbers(new int[][]{{36376, 85652, 21002, 4510}, {68246, 64237, 42962, 9974}, {32768, 97721, 47338, 5841}, {55103, 18179, 79062, 46542}}));
        intersection(new int[]{1,1,2},new int[]{2,3});
        singleNumber(new int[]{1,1,2});
        xorOperation(5,0);
        System.out.println(minSubsequence(new int[]{4,3,10,9,8}));
//        ConcurrentHashMap;
//        HashMap
//        Hashtable
        numWaterBottles(15,4);
        String ac = "1";
        String ab = "1";
        System.out.println(ab == ac);
        System.out.println(repeatedSubstringPattern("abaababaab"));
        ArrayList list4 = new ArrayList();
        list4.add(1);
        list4.add(2);
        System.out.println(list4);
    }
    String s ;

    @Test
    public void test08(){
//        TreeNode n5 = new TreeNode(9);
//        TreeNode n4 = new TreeNode(9);
//        TreeNode n3 = new TreeNode(6);
        TreeNode n2 = new TreeNode(9);
        TreeNode n1 = new TreeNode(1,n2,null);
        System.out.println(isUnivalTree(n1));
        System.out.println(letterCombinations("23"));
        binaryTreePaths(n1);
        String s3 = "zs";
        String s4 = "zs";
        String s5 = "zszs";
        String s6 = s3 + s4;
        System.out.println(s5 == s6);
        PrintMinNumber(new int[]{3334,3,3333332});
        System.out.println(-5%-2);
        System.out.println(-5%2);
        System.out.println(5%-2);
        System.out.println(5%2);
        System.out.println("s=" + s);
        ListNode a = new ListNode(1);
        ListNode b = new ListNode(1);
        System.out.println(mergeTwoLists(a,b));
        List list = new ArrayList();
        list.add(1);
        list.add(1);
        list.add(1);
        list.add(1);
        for (Object o : list) {
            System.out.println(o);
//            list.remove(0);
        }
        System.out.println(list);
        xiaobai(10);
        ListNode n13 = new ListNode(7);
        ListNode n12 = new ListNode(3);
        ListNode n11 = new ListNode(9);
        n11.next = n12;   n12.next = n13;

        ListNode n22 = new ListNode(3);
        ListNode n21 = new ListNode(6);
        n21.next = n22;
        addInList(n11,n21);
    }
    @Test
    public void test09() throws IOException {
        //ObjectOutputStream objectOutputStream = new ObjectOutputStream(new FileOutputStream(""));
//        int[][] arr = new int[3][];
//        for (int[] ints : arr) {
//            for (int anInt : ints) {
//                System.out.print(anInt + "");
//            }
//            System.out.println();
//        }
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        node1.left = node2; node1.right = node3;
        threeOrders(node1);
        System.out.println(Math.sqrt(2));
        //System.out.println(sqrt(1518991037));
        System.out.println(759495514 * 759495514);
        System.out.println(759495515 * 759495515);
        sqrt(7);
        push(1);
        push(2);
        push(3);
        System.out.println(pop());
        push(4);
        System.out.println(pop());
        push(5);
        System.out.println(pop());
        FindNumbersWithSum(new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20},21);
        DividedOldAndEven(new int[]{1,2,5,6,7,8,10,0,3});
        intersect(new int[]{1,2},new int[]{1,2});
        majorityElement(new int[]{3,2,3});
        System.out.println(reservestr("abcde",5));
    }
    int jiecheng(int i) {//计算阶乘
        if (i == 1)
            return 1;
        else
            return i * jiecheng(i - 1);
    }
    @Test
    public void test11(){
        double a = 0.1;
        double b= 0.2;
        double c= a + b;
        System.out.println(c);
    }
    @Test
    public void test10(){
        double x = 2;
        double result;
        result = Math.sin(x);
        boolean flag = true;
        int i = 3;
        //cout << jiecheng(3) << "@" << pow(2, 3);
        System.out.println(1e-6);
        while (Math.abs(x - result) > 1e-6) {
            if (flag) {
                x = x - Math.pow(x, i) / jiecheng(i);
                double temp = Math.pow(x, i) / jiecheng(i);;
                i += 2;
            }
            else{
                x = x + Math.pow(x, i) / jiecheng(i);
                double temp = Math.pow(x, i) / jiecheng(i);;
                i += 2;
            }
            flag = !flag;
        }
        System.out.println("sinx:"+result+"     x:"+x);
        System.out.println(fun2(4));
        double sum = 0;
        for (int i1 = 0; i1 < 5; i1++) {
            int fenmu =  fun2(i1+1) ;
            double temp = (double)1 / fenmu;
            sum += temp;
        }
        System.out.println(sum);
    }
    public void test01(){
        List<Integer> list = new ArrayList<Integer>();
        for (Integer integer : list) {

        }
    }
    public void test02(){
        Queue<Integer> queue;
    }
    int fun2(int n) {
        if (n == 1)
            return 1;
        else
            return n + fun2(n - 1);
    }

    public String reservestr(String str, int length){
        if(length == 1){
            return String.valueOf(str.charAt(length-1));
        }
        return String.valueOf(str.charAt(length-1)) + reservestr(str,--length);
    }
    public int[] DividedOldAndEven(int [] array){
        int[] resArray = new int[array.length];
        int begin = 0;
        int end = array.length-1;
        for (int a : array) {
            if(a % 2 == 0){
                //偶数
                resArray[end--] = a;
            }else{
                //奇数
                resArray[begin++] = a;
            }
        }
        return resArray;

    }
    public Node connect(Node root) {
        if(root == null)
            return null;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            Node pre = null;
            for(int i = 0;i < size; i++){
                Node node = queue.poll();
                if (pre != null)
                    pre.next = node;
                pre = node;
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
        }
        return root;
    }
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;
        public Node() {}
        public Node(int _val) {
            val = _val;
        }
        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };
    public boolean uniqueOccurrences(int[] arr) {
        Map<Integer,Integer> map = new HashMap<>();
        Arrays.sort(arr);
        int pre = arr[0];
        map.put(pre,1);
        for(int i = 1; i < arr.length; i++){
            if(arr[i] == pre){
                map.put(arr[i], map.get(arr[i]) + 1);
            }else{
                map.put(arr[i], 1);
            }
            pre = arr[i];
        }
        List<Integer> list = new ArrayList<>();
        for(Integer value : map.values()){
            if (list.contains(value))
                return false;
            else list.add(value);
        }
        return true;
    }
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int j = 0;
        int last = nums[0];
        for(int i=0; i< nums.length; i++){
            if(nums[i] == last){
                j++;
                if(j > nums.length/2){
                    return last;
                }
            }else{
                j = 0;
                last = nums[i];
            }
        }
        return -1;
    }
    int sum;
    int depth;
    public int deepestLeavesSum(TreeNode root) {
        depth = depth(root);
        dfs3(root,1);
        return sum;
    }
    public void dfs3(TreeNode root, int level){
        if (root == null)
            return;
        if (level == depth)
            sum += root.val;
        dfs3(root.left,level+1);
        dfs3(root.right,level+1);
    }
    public int depth(TreeNode root){
        if(root  == null)
            return 0;
        return 1+Math.max(depth(root.left),depth((root.right)));
    }
    int[] nums;
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        this.nums = nums;
        return helper(0, nums.length);
    }
    public TreeNode helper(int start, int end){
        if(start >= end)
            return null;
        int max = nums[start];
        int index = start;
        for (int i = start + 1; i < end; i++) {
            if (nums[i] > max){
                max = nums[i];
                index = i;
            }
        }
        TreeNode node = new TreeNode(max);
        node.left = helper(start,index);
        node.right = helper(index+1,end);
        return node;
    }
    public int diagonalSum(int[][] mat) {
        int sum = 0;
        int left = 0;
        int right = mat.length-1;
        for (int i = 0; i < mat.length; i++) {
            sum += mat[i][left++];
            sum += mat[i][right--];
        }
        if (mat.length % 2 != 0){
            sum -= mat[mat.length/2][mat.length/2];
        }
        return sum;
    }
    public int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap();
        for (int i1 : nums1) {
            if (map.get(i1) == null)
                map.put(i1,1);
            else
                map.put(i1,map.get(i1)+1);
        }
        for (int i1 : nums2) {
            if (map.get(i1) != null){
                list.add(i1);
                if (map.get(i1) == 1){
                    map.remove(i1);
                }
                else {
                    map.put(i1,map.get(i1)-1);
                }
            }
        }
        int[] array = new int[list.size()];
        for (int i = 0; i < array.length; i++) {
            array[i] = list.get(i);
        }
        return array;
    }
    /*
    输入: [3,1,3,4,2]
    输出: 3
     */
    public int findDuplicate(int[] nums) {
        Map map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            if (map.get(nums[i]) == null)
                map.put(nums[i],1);
            else
                return nums[i];
        }
        return -1;
    }
    /*
    输入：candidates = [2,3,5], target = 8,
    所求解集为：
    [
      [2,2,2,2],
      [2,3,3],
      [3,5]
    ]   放弃
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> resList = new ArrayList<>();
        for(int i=candidates.length-1; i>=0; i++){
            if(candidates[i] > target)  continue;
            if(candidates[i] == target){
                List<Integer> list = new ArrayList<>();
                list.add(candidates[i]);
                resList.add(list);
            }
            if(candidates[i] < target){

            }
        }
        return null;
    }
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        int left = 0;
        int right = array.length-1;
        Map<Integer,Integer> map = new HashMap<>();
        while(left <= right){
            if(array[left] + array[right] == sum){
                map.put(array[left],array[right]);
                left ++;
                right --;
            }else if(array[left] + array[right] < sum){
                left++;
            }else{
                right--;
            }
        }
        if (map.isEmpty()){
            return list;
        }
        Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
        int total = Integer.MAX_VALUE;
        int a1 = 0;
        int a2 = 0;
        while(iterator.hasNext( )) {
            Map.Entry<Integer, Integer> entry = iterator.next();
            int key = entry.getKey( );
            int value = entry.getValue();
            if(key * value < total){
                total = key * value;
                a1 = key;
                a2 = value;
            }
        }
        list.add(a1);
        list.add(a2);
        return list;
    }
    public int maxLength (int[] arr) {
        // write code here
        if (arr.length <= 1)
            return arr.length;
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            Map<Integer,Integer> map = new HashMap();
            for (int j = i; j < arr.length; j++) {
                if (map.get(arr[j]) == null){
                    map.put(arr[j],1);
                }else
                    break;
            }
            int size = map.size();
            if (size > max)
                max = size;
        }
        return max;
    }
    public boolean isValid (String s) {
        // write code here
        if(s.length() % 2 == 1)
            return false;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(')
                stack.push(')');
            else if (c == '[')
                stack.push(']');
            else if (c == '{')
                stack.push('}');
            else if (stack.isEmpty() || stack.pop() != c)
                return false;
        }
        return stack.isEmpty();
    }
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public void push(int node) {
        stack1.push(node);

    }
    public int pop() {
        while(stack1.size() > 0){
            int node = stack1.pop();
            stack2.push(node);
        }
        int res = stack2.pop();
        while (stack2.size() > 0){
            int node = stack2.pop();
            stack1.push(node);
        }
        return res;
    }
    public int sqrt (int x) {
        int l = 1;
        int r = x;
        while(l <= r){    //7
            int mid = (r + l)/2;    //4    2            3
            if(x/mid > mid){    //7/4=1 4    7/2=3
                l = mid + 1;    //    l=3
            } else if(x / mid < mid){
                r = mid - 1;    //    r=3
            } else  if(x/mid == mid){
                return mid;
            }
        }
        return r;//返回小的
//        // write code here
//        if(x == 0)
//            return 0;
//        if(x == 1)
//            return 1;
//        for(double i = x / 2; i > 0; i --){
//            if(i * i <= x && (i+1) * (i+1) > x){
//                String s = i+"";
//                return Integer.parseInt((s).substring(0,s.length()-2));
//            }
//        }
//        return -1;
    }
    public int[][] threeOrders (TreeNode root) {
        // write code here
        int count = count(root);
        int[][] arr = new int[3][count];
        fds1(arr, root);
        fds2(arr, root);
        fds3(arr, root);
        return arr;
    }

    public int count(TreeNode root){
        if(root == null){
            return 0;
        }
        return 1 + count(root.left) + count(root.right);
    }

    public int i = 0;
    public void fds1(int[][] arr, TreeNode root){
        if(root == null)
            return;
        arr[0][i++] = root.val;
        fds1(arr,root.left);
        fds1(arr,root.right);
    }
    int j = 0;
    public void fds2(int[][] arr, TreeNode root){
        if(root == null)
            return;
        fds2(arr,root.left);
        arr[1][j++] = root.val;
        fds2(arr,root.right);
    }
    int k = 0;
    public void fds3(int[][] arr, TreeNode root){
        if(root == null)
            return;
        fds3(arr,root.left);
        fds3(arr,root.right);
        arr[2][k++] = root.val;
    }
    /*
    [9,3,7],[6,3]
    {1,0,0,0}
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        int sum1 = 0;
        int sum2 = 0;
        while (head1 != null){
            sum1 = sum1 * 10 + head1.val;
            head1 = head1.next;
        }
        while (head2 != null){
            sum2 = sum2 * 10 + head2.val;
            head2 = head2.next;
        }
        String result = sum1 + sum2 + "";
        ListNode node = new ListNode(Integer.parseInt(String.valueOf(result.charAt(0))));
        ListNode temp = node;
        if (Integer.parseInt(result) < 10){
            return node;
        }else {
            for (int i = 1; i < result.length(); i++) {
                int value = Integer.parseInt(String.valueOf(result.charAt(i)));
                ListNode next = new ListNode(0);
                next.val = value;
                temp.next = next;
                temp = temp.next;
            }
            return node;
        }
    }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        List<ListNode> list = new ArrayList<>();
        while (pHead1 != null){
            list.add(pHead1);
            pHead1 = pHead1.next;
        }
        while (pHead2 != null){
            if (!list.contains(pHead2))
                pHead2 = pHead2.next;
            else
                break;
        }
        return pHead2;
    }
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        int count = 0;
        ListNode node = head;
        while(node != null){
            count++;
            node = node.next;
        }
        if(count == 1){
            return null;
        }
        if(count == 2){
            //n == 1 ? (head = head.next) : (head.next = null);
            if(n == 1){
                head.next = null;
            }else{
                head = head.next;
            }
            return head;
        }
        int index = 0;
        node = head;
        if(count == n){
            return head.next;
        }else{
            while(index != count - n - 1){
                index++;
                node = node.next;
            }
            ListNode pre = node;
            ListNode next = pre.next.next;
            pre.next = next;
        }
        return head;
    }
    public void xiaobai(int length)   {
        if (length <= 1){
            System.out.println("放入一块肉，长度是："+length);
            return;
        }
        xiaobai(length / 2);
        xiaobai(length - length / 2);
        Boolean flag = true;
        if (flag = false)
        {
            System.out.println("true");
        }
        else
        {
            System.out.println("false");
        }

    }
    public static double max(int x, int y) {
        return 0.0;
    }
    public int max(double a, int b) {
        return 0;
    }
    class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int i) {
            this.val = i;
        }

        public ListNode() {

        }
    }
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        if(l1 == null && l2 == null)
            return null;
        if(l1 == null)
            return l2;
        if(l2 == null)
            return l1;
        ListNode node = new ListNode(1);
        ListNode res = node;
        ListNode leftIndex = l1;
        ListNode rightIndex = l2;
        while(leftIndex != null || rightIndex != null){
            if(leftIndex == null){
                node.next = rightIndex;
                break;
            }else if(rightIndex == null){
                node.next = leftIndex;
                break;
            }else if(leftIndex.val <= rightIndex.val){
                node.next = leftIndex;
                leftIndex = leftIndex.next;
                node = node.next;
            }else if (rightIndex.val < leftIndex.val){
                node.next = rightIndex;
                rightIndex = rightIndex.next;
                node = node.next;
            }
        }
        return res.next;
    }
    public String PrintMinNumber(int [] numbers) {
        //排序规则
        for(int i = 0; i < numbers.length; i++){
            for(int j = 0; j < numbers.length-i-1; j++){
                String s1 = numbers[j]+""+numbers[j+1];
                String s2 = numbers[j+1]+""+numbers[j];
                double i1 = Double.valueOf(s1);
                double i2 = Double.valueOf(s2);
                if(i1 > i2){
                    int temp = 0;
                    temp = numbers[j];
                    numbers[j] = numbers[j+1];
                    numbers[j+1] = temp;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int num : numbers){
            sb.append(num);
        }
        return sb.toString();
//        Stack
    }
    List<String> res = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null)
            return res;
        dfs3(root,"");
        return res;
    }
    public void dfs3(TreeNode root,String s){
        if (root.left == null && root.right == null){
            res.add(s+root.val);
        }
        String str = s+root.val;
        if (root.left != null){
            dfs3(root.left,str+"->");
        }
        if (root.right != null){
            dfs3(root.right,str+"->");
        }
    }
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> queue = new ArrayDeque();
        if (root !=null)
            queue.add(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            Double sum = 0.0;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null){
                    queue.add(node.right);
                }
            }
            res.add((sum / size));
        }
        return res;
    }
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();

        Queue<TreeNode> queue = new ArrayDeque<>();
        if (root != null)
            queue.add(root);

        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null){
                    queue.add(node.right);
                }
            }
            res.add(0,list);
        }
        return res;
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();

        Queue<TreeNode> queue = new ArrayDeque<>();
        if (root != null)
            queue.add(root);

        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null){
                    queue.add(node.right);
                }
            }
            res.add(list);
        }
        return res;
    }
    /*
            9 831
       9 833        6
 9 838    9
     */
    public boolean isUnivalTree(TreeNode root) {
        return dfs2(root,root.val);
    }
    public boolean dfs2(TreeNode root, int val){
        if (root == null){
            return true;
        }
        if(root.val != val){
            return false;
        }
        return dfs2(root.left,val) && dfs2(root.right,val);
    }
    private List<String> resList = new ArrayList<String>();
    Map<String,String> map = new HashMap<String,String>();

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0 || digits == null)
            return resList;
        map.put("2","abc");
        map.put("3","def");
        map.put("4","ghi");
        map.put("5","jkl");
        map.put("6","mno");
        map.put("7","pqrs");
        map.put("8","tuv");
        map.put("9","wxyz");
        jointResult(digits, 0, "");
        return resList;
    }

    private void jointResult(String digits, int index, String curStr) {
        if (index == digits.length()) {
            resList.add(curStr);
            return;
        }
        int i1 = Integer.parseInt(digits.charAt(index) + "");
        String s = map.get(i1+"");
        char[] curChars = s.toCharArray(); // 查询 当前数字 的 数组元素组成
        for (int i = 0; i < curChars.length; i++) { // 将 当前数字 的数组元素 逐一拼接，并遍历 下一个数字
            jointResult(digits, index + 1, curStr + curChars[i]);
        }
    }
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root,0);
    }

    public int dfs(TreeNode node, int val){
        if(node == null){
            return 0;
        }
        val = val * 2 + node.val;
        if(node.left == null && node.right == null){
            return val;
        }
        return dfs(node.left,val)+dfs(node.right,val);

    }
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for(int r = n/2; r >= 1; r--){  //abaab abaab  r=5 n=10
            if(n % r == 0){
                String substring = s.substring(0, r);   //abaab
                StringBuilder sb = new StringBuilder();
                for(int i = 0; i < n / r; i++){ // n/r=10/5=2
                    sb.append(substring);
                }
                if(sb.toString().equals(s)) return true;
            }
        }
        return false;
    }
    public int numWaterBottles(int numBottles, int numExchange) {
        int ans = 0;
        int emptyBottles = 0;

        while (numBottles > 0) {
            ans += numBottles;  //喝掉
            emptyBottles += numBottles; //空瓶加起来
            numBottles = emptyBottles / numExchange;    //兑换新的
            emptyBottles = emptyBottles % numExchange;  //换完新的还剩下多少空的？
        }
        return ans;
        /**
         * emp=0
 *         drk=0
 *
 *         while emp>=numExchange or numBottles>0: #空瓶还能换 或 还有酒没喝
 *             drk+=numBottles # 喝掉
 *             emp+=numBottles # 空瓶加起来
 *             numBottles=emp//numExchange # 换酒
 *             emp=emp%numExchange # 剩多少空瓶？
 *         return drk
         *
         */

//        int count = 0;
//        int more = 0;
//        while(numBottles > 0){
//            count += numBottles;
//            /**
//             * //  10/3 = 3    4/3=1   2/3=0
//             * //  10%3 = 1    4%3=1   2%3=2
//             */
//            more += numBottles % numExchange;
//            numBottles = numBottles / numExchange;
//
////            if(numBottles + more >= numExchange){
////                count++;
////                more = 0;
////                numBottles = (numBottles + more) / numExchange;
////            }
//            if (more >= numExchange){
//                count++;
//                more = more % numExchange;
//            }
//        }
//        return count;
    }
    public List<Integer> minSubsequence(int[] nums) {
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        //[3,4,8,9,10]
        for (int i = nums.length-1; i >= 0 ; i--){
            int after = 0;
            for (int j = i; j < nums.length ; j++) {
                after += nums[j];
            }
            if (after > sum/2){
                int end = nums.length-1;
                while (end >= i){
                    list.add(nums[end]);
                    end--;
                }
                return list;
            }
        }
//        for (int i = nums.length-1; i >= 0 ; i--){
//            int after = 0;
//            int before = 0;
//            for (int j = i; j < nums.length ; j++) {
//                after += nums[j];
//            }
//            for (int j = i-1; j >= 0; j--) {
//                before += nums[j];
//            }
//            if (after > before){
//                int end = nums.length-1;
//                while (end >= i){
//                    list.add(nums[end]);
//                    end--;
//                }
//                return list;
//            }
//        }
        return null;
    }
    public int xorOperation(int n, int start) {
        int sum = 0;
        int end = start + 2*(n-1);
        while (start <= end ){
            sum ^= start;
            start += 2;
        }
        return sum;
    }
    public int singleNumber(int[] nums) {
        Set list = new HashSet();
        for (int num : nums) {
            boolean add = list.add(num);
            if (!add){
                list.remove(num);
            }
        }
        Object[] objects = list.toArray();
        return (int) objects[0];
    }
    public int[] intersection(int[] nums1, int[] nums2) {
        Set set1 = new HashSet();
        Set set2 = new HashSet();
        for (int i : nums1) {
            set1.add(i);
        }
        for (int i : nums2) {
            if (set1.contains(i)){
                set2.add(i);
            }
        }
        int[] res = new int[set2.size()];
        int i = 0;
        for (Object o : set2) {
            res[i++] = (int) o;
        }
        int a =1;
        return res;
    }
    /*
    输入：matrix = [[3,7,8],[9,11,13],[15,16,17]]
    输出：[15]
    解释：15 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。
     */
    public List<Integer> luckyNumbers (int[][] matrix) {
        List<Integer> list = new ArrayList();
        List<Integer> list2 = new ArrayList();
        for (int i = 0; i < matrix.length; i++) {
            //遍历每一行，取出最小值
            int min = matrix[i][0];
            for (int matrix1 : matrix[i]) {
                if (matrix1 < min){
                    min = matrix1;
                }
            }
            list2.add(min);
        }
        Collections.sort(list2);
        list.add(list2.get(list2.size()-1));
        int a = 1;
        return list;
    }
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
        int count = 0;
        for (int i : arr1) {
            boolean flag = true;
            for (int arr : arr2) {
                if (Math.abs(i-arr) <= d){
                    flag = false;
                }
            }
            if (flag){
                count++;
            }
        }
        return count;
    }
    public String sortString(String s) {
        StringBuilder sb = new StringBuilder();
        Map<Character,Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            if (map.get(aChar) == null){
                map.put(aChar,1);
            }else {
                map.put(aChar,map.get(aChar)+1);
            }
        }
        while (map.size() > 0){
            List<Character> list = new ArrayList<>();
            boolean flag = true;
            while (flag){
                flag = false;
                char min = '|';
                for (Character character : map.keySet()) {
                    if (character < min && !list.contains(character)){
                        min = character;
                        flag = true;
                    }
                }
                if (flag){
                    list.add(min);
                    //更新map
                    Integer integer = map.get(min);
                    if (integer <= 1){
                        map.remove(min);
                    }else {
                        map.put(min,integer - 1);
                    }
                    //追加最小的字符
                    sb.append(min);
                }
            }

            //选最大
            List<Character> list2 = new ArrayList<>();
            boolean flag2 = true;
            while (flag2){
                flag2 = false;
                char max = '0';
                for (Character character : map.keySet()) {
                    if (character > max && !list2.contains(character)){
                        max = character;
                        flag2 = true;
                    }
                }
                if (flag2){
                    list2.add(max);
                    //更新map
                    Integer integer = map.get(max);
                    if (integer <= 1){
                        map.remove(max);
                    }else {
                        map.put(max,integer - 1);
                    }
                    //追加最大的字符
                    sb.append(max);
                }
            }
        }
        return sb.toString();
    }
    public boolean divisorGame(int N) {
        int i = 0;
        while (N > 1){
            for (int j = 1; j < N; j++) {
                if (N % j == 0){
                    i++;
                    N = N - j;
                    break;
                }
            }
        }
        return i%2==1?true:false;
    }
    public int arrayPairSum(int[] nums) {
        quickSort(nums,0,nums.length-1);
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0){
                count += nums[i];
            }
        }
        return count;
    }
    //快速排序
    public void quickSort(int[] arr, int begin, int end){
        //校验：递归终止条件
        if (arr.length <= 1 || begin >= end){
            return;
        }
        //进行分区得到分区下标
        int pivotIndex = partition(arr,begin,end);
        //递归，左侧快排
        quickSort(arr,begin,pivotIndex-1);
        //递归，右侧快排
        quickSort(arr,pivotIndex+1,end);
        System.out.println(Arrays.toString(arr));
    }
    private int partition(int[] arr, int begin, int end){
        int pivot = arr[end];
        int pivotIndex = begin;
        for (int i = begin; i < end; i++) {
            if (arr[i] < pivot){
                if (i > pivotIndex){
                    swap(arr,i,pivotIndex);
                }
                pivotIndex++;
            }
        }
        swap(arr,pivotIndex,end);
        return pivotIndex;
    }
    private void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public int heightChecker(int[] heights) {
        //heights = [1,1,4,2,1,3]
        int count = 0;
        int[] arr = Arrays.copyOf(heights,heights.length);
        Arrays.sort(arr);
        for (int i = 0; i < heights.length; i++) {
            if (arr[i] != heights[i]){
                count++;
            }
        }
        return count;
    }
    /*
    输入：s = "8910#11#12"
    输出："jkab"
    解释："j" -> "10#" , "k" -> "11#" , "a" -> "1" , "b" -> "2".
     */
    public String freqAlphabets(String s) {
        int i = 0;
        StringBuilder sb = new StringBuilder();
        while (i < s.length()){
            if (i < s.length()-2 && s.charAt(i+2) == '#'){
                char c = (char) ('a' + Integer.parseInt(s.substring(i, i + 2)) - 1);
                sb.append(c);
                i = i + 3;
            }else {
                char c = (char) ('a' + Integer.parseInt(s.charAt(i)+"") - 1);
                sb.append(c);
                i++;
            }
        }
        return sb.toString();
    }
    public List<Integer> selfDividingNumbers(int left, int right) {
        List<Integer> list = new ArrayList<>();
        while (left <= right){
            if (left <= 9){
                list.add(left);
            }else {
                boolean flag = true;
                String str = left+"";
                for (int i = 0; i < str.length(); i++) {
                    int anInt = Integer.parseInt(String.valueOf(str.charAt(i)));
                    if (anInt == 0 || left % anInt != 0 ){
                        flag = false;
                        break;
                    }
                }
                if (flag){
                    list.add(left);
                }
            }
            left ++;
        }
        return list;
    }
    public int[] sumZero(int n) {
        int[] result = new int[n];
        int left = 0;
        int right = 0;
        if (n % 2 == 0){
            left = n/2 - 1;
            right = n/2;
            int i = 1;
            while (left >= 0){
                result[left] = -i;
                i++;
                left--;
            }
            while (right < n){
                result[right] = i;
                i--;
                right++;
            }
        }else {
            result[n/2] = 0;
            left = n/2 - 1;
            right = n/2 + 1;
            int i = 1;
            while (left >= 0){
                result[left] = -i;
                i++;
                left--;
            }
            while (right < n){
                result[right] = i;
                i--;
                right++;
            }
        }
        return result;
    }
    public boolean judgeCircle(String moves) {
        int count1 = 0;
        int count2 = 0;
        for (int i = 0; i < moves.length(); i++) {
            if (moves.charAt(i) == 'L')
                count1++;
            if (moves.charAt(i) == 'R')
                count1--;
            if (moves.charAt(i) == 'U')
                count2++;
            if (moves.charAt(i) == 'D')
                count2--;
        }
        if (count1 == 0 && count2 == 0)
            return true;
        else
            return false;
    }
    List<Object> list1 = new ArrayList<Object>();
    List<Object> list2 = new ArrayList<Object>();
    public boolean isSameTree(TreeNode p, TreeNode q) {
        search(p);
        search2(q);
        boolean flag = true;
        if(list1.size() != list2.size()) {
            return false;
        }
        for (int i = 0; i < list1.size(); i++) {
            if (list1.get(i) != list2.get(i)){
                return false;
            }
        }
        return flag;
    }
    public void search(TreeNode p){
        if (p == null){
            return;
        }
        if(p.left == null && p.right == null){
            list1.add(p.val);
            return;
        }
        list1.add(p.val);
        if (p.left == null && p.right != null){
            list1.add("");
        }
        if(p.left != null){
            search(p.left);
        }
        if(p.right != null){
            search(p.right);
        }
    }
    public void search2(TreeNode p){
        if (p == null){
            return;
        }
        if(p.left == null && p.right == null){
            list2.add(p.val);
            return;
        }
        list2.add(p.val);
        if (p.left == null && p.right != null){
            list2.add("");
        }
        if(p.left != null){
            search2(p.left);
        }
        if(p.right != null){
            search2(p.right);
        }
    }
public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode() {}
  TreeNode(int val) { this.val = val; }
  TreeNode(int val, TreeNode left, TreeNode right) {
      this.val = val;
      this.left = left;
      this.right = right;
  }
}
    public int maximum69Number (int num) {
        String s = num + "";
        s = s.replaceFirst("6","9");
        return Integer.valueOf(s);
    }
    public void reverseString(char[] s) {
        String s1 = new String(s);
        StringBuffer stringBuffer = new StringBuffer(s1);
        String s2 = stringBuffer.reverse().toString();
        char[] chars = s2.toCharArray();
        //s = chars;
//        Arrays.copyOf()
        for (int i = 0; i < s.length; i++) {
            s[i] = chars[i];
        }
        int a=1+1;
    }
    public boolean canBeEqual(int[] target, int[] arr) {
        for (int i = 0; i < target.length; i++) {
            int temp = 0;
            boolean flag = false;
            for (int j = 0; j < target.length-i-1; j++) {
                if (target[j] > target[j+1]){
                    temp = target[j];
                    target[j] = target[j+1];
                    target[j+1] = temp;
                }
            }
            if (flag == true){
                break;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            int temp = 0;
            boolean flag = false;
            for (int j = 0; j < arr.length-i-1; j++) {
                if (arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if (flag == true){
                break;
            }
        }
        if (Arrays.equals(target,arr)){
            return true;
        }else {
            return false;
        }
    }
    String result = "";
    public String removeDuplicates(String S) {
        result = S;
        return fun(S);
    }
    public String fun(String S){
        result = S;
        if (S.length() == 2){
            if( (S.charAt(0)+"").equals( (S.charAt(1)+"") )){
                result = "";
            }else {
                result = S;
            }
            return "";
        }
        if (S.length() < 2){
            result = S;
            return "";
        }
        boolean flag = false;
        for(int i=0;i<S.length()-1;i++){
            if( (S.charAt(i)+"").equals( (S.charAt(i+1)+"") )){
                flag = true;
                String str = S.substring(0,i) + S.substring(i+2,S.length());
                fun(str);
            }
        }
        return result;
    }
    /*
    nums =
    [[1,2],
     [3,4]]
    r = 1, c = 4
    输出:
    [[1,2,3,4]]
     */
    public int[][] matrixReshape(int[][] nums, int r, int c) {
        if (nums.length * nums[0].length != r * c){
            return nums;
        }
        int[][] result = new int[r][c];
        List<Integer> list = new ArrayList<>();
        for (int[] num : nums) {
            for (int i : num) {
                list.add(i);
            }
        }
        int index = 0;
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                result[i][j] = list.get(index++);
            }
        }
        return result;
    }
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] result  = new int[nums1.length];
        for(int i=0;i<nums1.length;i++){
            boolean flag2 = false;
            for(int j=0;j<nums2.length;j++){
                if(nums1[i] == nums2[j]){
                    flag2 = true;
                    boolean flag = false;
                    for(int k=j+1;k<nums2.length;k++){
                        if(nums2[k] > nums1[i]){
                            result[i] = nums2[k];
                            flag = true;
                            break;
                        }
                    }
                    if(flag == false){
                        result[i] = -1;
                    }
                    break;
                }
            }
            if(flag2 == false){
                result[i] = -1;
            }

        }
        return result;
    }
    public int oddCells(int n, int m, int[][] indices) {
        int count = 0;
        int[][] result = new int[n][m];
        Map<Integer,Integer> rowMap = new HashMap();
        Map<Integer,Integer> colMap = new HashMap();
        for (int i = 0; i < indices.length; i++) {
            // [0,1]    [1,1]
            for (int j = 0; j < indices[i].length; j++) {
                // 0  1
                if (j == 0){
                    //增加行
                    int row = indices[i][j]; //这个是要增加的行
                    if (rowMap.get(row) == null){
                        rowMap.put(row,1);
                    } else {
                        rowMap.put(row,rowMap.get(row)+1);
                    }
                }else {
                    // 增加列
                    int col = indices[i][j]; //这个是要增加的行
                    if (colMap.get(col) == null){
                        colMap.put(col,1);
                    } else {
                        colMap.put(col,colMap.get(col)+1);
                    }
                }
            }
        }
        for (Map.Entry<Integer, Integer> integerIntegerEntry : rowMap.entrySet()) {
            // 0,1  1,1
            for (int i = 0; i < result.length; i++) {
                // [0,1]    [1,1]
                if (i == integerIntegerEntry.getKey()){
                    for (int j = 0; j < result[i].length; j++) {
                        // 0  1
                        result[i][j] += integerIntegerEntry.getValue();
                    }
                }
            }
        }
        for (Map.Entry<Integer, Integer> integerIntegerEntry : colMap.entrySet()) {
            // 0,1  1,1
            for (int i = 0; i < result.length; i++) {
                // [0,1]    [1,1]
                for (int j = 0; j < result[i].length; j++) {
                    // 0  1
                    if (j == integerIntegerEntry.getKey()){
                        result[i][j] += integerIntegerEntry.getValue();
                    }
                }
            }
        }
        for (int[] ints : result) {
            for (int anInt : ints) {
                if (anInt % 2 != 0){
                    count++;
                }
            }
        }
        return count;
    }
    public static boolean canMakeArithmeticProgression(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int temp = 0;
            boolean flag = true;
            for (int j = 0; j < arr.length-i-1; j++) {
                if (arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = false;
                }
            }
            if (flag == true){
                break;
            }
        }
        int sub = Math.abs(arr[1] - arr[0]);
        for (int i = 2; i < arr.length; i++) {
            if (  Math.abs(arr[i] - arr[i-1]) != sub )
                return false;
        }
        return true;
    }
    public int hammingDistance(int x, int y) {
        double a = Math.log(x) / Math.log(2);
        double b = Math.log(y) / Math.log(2);
        return (int) Math.abs(a - b);
    }
    /*
    输入："(()())(())"
    输出："()()()"
    解释：
    输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
    删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
     */
    public String removeOuterParentheses(String S) {
        int count = 0;
        String result = "";
        int index = 0;
        for (int i = 0; i < S.length(); i++) {
            String s = S.charAt(i) + "";
            //( + 1  , ) - 1
            if (s.equals("("))
                count++;
            if (s.equals(")"))
                count--;
            if (count == 0 ){
                String yuanyu = S.substring(index,i+1);
                result += yuanyu.substring(1,yuanyu.length()-1);
                index = i+1;
            }
        }
        return result;
    }
    public int minTimeToVisitAllPoints(int[][] points) {
        int count = 0;
        for (int i = 0; i < points.length-1; i++) {
            int max = 0;
            for (int j = 0; j < points[i].length; j++) {
                if ( Math.abs( points[i][j] - points[i+1][j] ) > max ){
                    max = Math.abs( points[i][j] - points[i+1][j] );
                }
            }
            count += max;
        }
        return count;
    }
    public String restoreString(String s, int[] indices) {
        String[] result = new String[indices.length];
        char[] chars = s.toCharArray();
        for (int i = 0; i < indices.length; i++) {
            //Integer.parseInt(chars[i]+"")
            result[indices[i]] = chars[i]+"";
        }
//        return result.toString();
        return Arrays.toString(result).replace(",","").replace("[","").replace("]","").replace(" ","");
//        return String.valueOf(result);
    }
    public int findNumbers(int[] nums) {
        int count = 0;
        for(int i=0;i<nums.length;i++){
            if ((nums[i]+"").length() % 2 == 0){
                count++;
            }
        }
        return count;
    }
    public int[] createTargetArray(int[] nums, int[] index) {
        int[] target = new int[nums.length];
        for(int i=0;i<nums.length;i++){
            if(target[index[i]] != 0){
                for(int j=nums.length-1;j>index[i];j--){
                    target[j] = target[j-1];
                }
                target[index[i]] = nums[i];
            }else{
                target[index[i]] = nums[i];
            }

        }
        System.out.println(target);
        return target;
    }
    public int numberOfSteps (int num) {
        int count = 0;
        while(num >  0){
            if(num % 2 == 0){
                num = num / 2;
            }

            else{
                num--;
            }
            count++;
        }
        return count;
    }
    public int[] decompressRLElist(int[] nums) {
        String a = "";
        for(int i=0;i<nums.length;i=i+2){
            for(int j=0;j<nums[i];j++){
                a = a + nums[i+1];
            }
        }
        for (int i = 0; i < a.toCharArray().length; i++) {
            nums[i] = Integer.parseInt(String.valueOf(a.toCharArray()[i]));
        }
        return nums;
    }
    public int minCount(int[] coins) {
        int sum = 0;
        for (int coin : coins) {
            sum += coin/2;
            if (coin % 2 == 1){
                sum++;
            }
        }
        return sum;
    }
    public int subtractProductAndSum(int n) {
        String s = String.valueOf(n);
        int sum = 0;
        int multiply = 1;
        char[] chars = s.toCharArray();
        for (char c : chars) {
            sum += Integer.parseInt(String.valueOf(c));
            multiply *= Integer.parseInt(c+"");
        }
        return multiply - sum;
    }
    public int numJewelsInStones(String J, String S) {
        int count = 0;
        char[] j = J.toCharArray();
        //List<char[]> chars = Arrays.asList(j);
        List<Character> list = new ArrayList<Character>();
        for (char c : j) {
            list.add(c);
        }
        char[] s = S.toCharArray();
        for (char c : s) {
            if (list.contains(c)){
                count++;
            }
        }
        return count;
    }
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        List<Boolean> List = new ArrayList<Boolean>();
        int max = candies[0];
        for(int candie :candies){
            if (candie > max){
                max =  candie;
            }
        }
        for(int candie :candies){
            if(candie+extraCandies >= max){
                List.add(true);
            }else {
                List.add(false);
            }
        }
        return List;
    }

    public int[] shuffle(int[] nums, int n) {
        int[] temp = new int[nums.length];
        boolean flag = true;
        int count1 = 0;
        int count2 = 0;
        for(int i=0;i<nums.length;i++){
            if (flag == true){
                temp[i] = nums[count1];
                flag = false;
                count1++;
            }else {
                temp[i] = nums[nums.length/2 + count2];
                flag = true;
                count2++;
            }
        }

        return temp;
    }


    public String replaceSpace(StringBuffer str) {
        return str.toString().replace(" ","%20");
    }

    public void reOrderArray(int [] array) {
        int length = 0;
        int ji = 0;
        int ou = 0;
        for(int i=0;i<array.length;i++){
            if(array[i] % 2 == 1){
                //奇数
                ji++;
            } else{
                ou++;
            }
        }
        int[] left = new int[ji];
        int[] right = new int[ou];
        int lcount = 0;
        int rcount = 0;
        for(int i=0;i<array.length;i++){
            if(array[i] % 2 == 1){
                //奇数
                left[lcount] = array[i];
                lcount++;
            } else{
                right[rcount] = array[i];
                rcount++;
            }
        }
        int[] result = new int[array.length];
        for(int i=0;i<left.length;i++){
            result[i] = left[i];
        }
        int r = 0;
        for(int i=left.length;i<array.length;i++){
            result[i] = right[r];
            r++;
        }
        for(int i=0;i<array.length;i++){
            array[i] = result[i];
        }
    }
    public void reOrderArray2(int [] array) {
        int length = 0;
        int ji = 0;
        int ou = 0;
        length = (array.length)/2 ;
        if((array.length)/2 % 2 == 0){
            ji = length;
            ou = length;
        } else{
            ji = length + 1;
            ou = length;
        }
        int[] left = new int[ji];
        int[] right = new int[ou];
        int lcount = 0;
        int rcount = 0;
        for(int i=0;i<array.length;i++){
            if(i%2 == 0){
                left[lcount] = array[i];
                lcount++;
            } else{
                right[rcount] = array[i];
                rcount++;
            }
        }
        int[] result = new int[array.length];
        for(int i=0;i<left.length;i++){
            result[i] = left[i];
        }
        int r = 0;
        for(int i=left.length;i<array.length;i++){
            result[i] = right[r];
            r++;
        }
    }

    public int MoreThanHalfNum_Solution(int [] array) {
        Map<Integer,Integer> map = new HashMap();
        for(int i=0;i<array.length;i++){
            if(map.containsKey(array[i])){
                int sum = Integer.parseInt(String.valueOf(map.get(array[i]))) ;
                map.put(array[i],sum+1);
                if(sum+1 > array.length/2)
                    return array[i];
            } else{
                map.put(array[i],1);
            }
        }
        return 0;
    }
    public int Sum_Solution(int n) {
        int sum=0;
        for(int i=0;i<=n;i++){
            sum += i;
        }
        return sum;
    }

    public boolean duplicate(int numbers[],int length,int [] duplication) {
        Map map = new HashMap();
        for(int i=0;i<=length-1;i++){
            if(map.containsKey(numbers[i])){
                duplication[0] = numbers[i];
                return true;
            }else{
                map.put(numbers[i],"1");
            }
        }
        return false;
    }
    @Test
    public void test99() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        Class<? extends List> aClass = list.getClass();
        Method add = aClass.getMethod("add", Object.class);
        add.invoke(list,"hello");
        add.invoke(list,"java");
        System.out.println(list);
    }

    public void quickSort2(int[] arr,int begin, int end){
        if (arr.length < 2 || begin >= end)
            return ;
        int i = partition2(arr, begin, end);
        quickSort2(arr,begin,i-1);
        quickSort2(arr,i+1,end);
    }
    public int partition2(int[] arr,int begin, int end){
        int pivot = arr[end];
        int pivotIndex = begin;
        for (int i = begin; i < end; i++) {
            if (arr[i] < pivot){
                if (i > pivotIndex){
                    swap2(arr,i,pivotIndex);
                }
                pivotIndex++;
            }
        }
        swap2(arr,pivotIndex,i);
        return pivotIndex;
    }
    public void swap2(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public int[] guibing(int[] arr){
        if (arr.length < 2)
            return arr;
        int mid = arr.length;
        int[] left = Arrays.copyOfRange(arr,0,mid);
        int[] right = Arrays.copyOfRange(arr,mid,arr.length);
        int[] leftSort = guibing(left);
        int[] rightSort = guibing(right);
        return merge(leftSort,rightSort);
    }
    public int[] merge(int[] left,int[] right){
        int[] arr = new int[left.length+right.length];
        int lIndex = 0;
        int rIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            if (lIndex >= left.length){
                arr[i] = right[rIndex++];
            }else if (rIndex >= right.length) {
                arr[i] = left[lIndex++];
            }else if(left[lIndex] < right[rIndex]){
                arr[i] = left[lIndex++];
            }else{
                arr[i] = right[rIndex++];
            }
        }
        return arr;
    }

    public void charu(int[] arr){
        if (arr.length < 2)
            return;
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            for (int j = i-1; j >= 0 ; j--) {
                if (temp > arr[j]){
                    break;
                }else {
                    arr[j+1] = arr[j];
                }
            }
            arr[j+1] = temp;
        }
    }

    public void xuanze(int[] arr){
        if (arr.length < 2)
            return;
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            if (minIndex != i){
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

    public void maopao(int[] arr){
        if (arr.length < 2)
            return;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length-i-1; j++) {
                if (arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}
